First-in, first-out (FIFO) memories are a common component for buffering data in digital devices. In a conventional FIFO memory, data is stored or “pushed” into the memory in sequential locations. The data is then read or “popped” from the memory in the same order in which it was pushed into the memory. In other words, the first data stored in the memory is the first data read from the memory.
FIG. 2 illustrates conventional first-in, first-out (FIFO) memory 200 according to an exemplary embodiment of the prior art. In this example, memory 200 includes random access memory (RAM) 205, write pointer 210, read pointer 215, and comparator 220. Data is stored in RAM 205 during a “push” operation, where data is presented to RAM 205 and a PUSH signal is asserted. The data is then stored starting at the memory location identified by write pointer 210. Write pointer 210 is then incremented to point to the next starting memory location in RAM 205. When write pointer 210 reaches the last memory location in RAM 205, write pointer 210 is reset to point to the first memory location in RAM 205. In this way, incoming data is stored in RAM 205 in a circular fashion.
Data is read from RAM 205 during a “pop” operation. A POP signal is asserted, and data stored in the memory location identified by read pointer 215 is retrieved. The retrieved data is then output, and read pointer 215 is incremented to point to the next memory location in RAM 205. When read pointer 215 reaches the last memory location in RAM 205, read pointer 215 is reset to point to the first memory location in RAM 205. In this way, data is read from RAM 205 in a circular fashion.
Depending on how quickly the data is written to or read from RAM 205, write pointer 210 and read pointer 215 may point to the same memory location in RAM 205. Comparator 220 compares the memory locations output by write pointer 210 and read pointer 215 to determine when RAM 205 is full or empty. For example, when write pointer 210 is incremented, comparator 220 compares write pointer 210 and read pointer 215. If they are equal, this indicates that data has been stored in the last free memory location of RAM 205, and comparator 220 outputs a signal indicating that RAM 205 is full. Similarly, when read pointer 215 is incremented, comparator 220 compares write pointer 210 and read pointer 215. If they are equal, this indicates that data has been read from the last un-read memory location of RAM 205 and comparator 220 outputs a signal indicating that RAM 205 is empty.
A problem with conventional FIFO memories, such as the one shown in FIG. 2, is that RAM 205 takes up a large amount of space in an integrated circuit. RAM 205 also typically represents a large portion of the cost of the integrated circuit. Moreover, the data received by the FIFO memory is often contained in data packets, which may have variable sizes. To handle data packets of variable size, RAM 205 stores data packets in memory slots, where each slot is large enough to store the biggest data packet expected. To keep RAM 205 from overflowing, RAM 205 also typically includes a large number of memory slots for storing a large number of data packets. This typically increases the size of RAM 205, which also increases the size and cost of the integrated circuit that uses RAM 205. This also means that at least a portion of RAM 205 is often wasted because it is not used to store data.
Therefore, there is a need in the art of an improved buffer circuit for use in a network device. In particular, there is a need for an improved FIFO memory that efficiently buffers data packets of varying sizes in a router or other network device.